package hot100;

public class Solution5 {

    public String longestPalindrome1(String s) {
        int max = 0;
        int start = 0;
        int end = start;
        for (int i = 0; i <= 2 * (s.length() - 1); i++) {
            int left = i / 2;
            int right = (i % 2 == 0) ? left : left + 1;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if (right - left + 1 > max) {
                    start = left;
                    end = right;
                }
                left--;
                right++;
            }
        }
        return s.substring(start, end + 1);
    }

    public String longestPalindrome(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append("#").append(s.charAt(i));
        }
        s = stringBuilder.append("#").toString();

        int start = 0;
        int end = 0;
        int[] f = new int[s.length()];
        // 标记历史最右端力臂所到位置
        int right = -1;
        // 对称中心 j
        int j = -1;
        for (int i = 0; i < s.length(); i++) {
            // 当前i的力臂长度
            int cur_len;
            if (right >= i) {
                // i关于j的对称点k
                int k = j - (i - j);
                // 根据历史f[k],得到最小长度
                int min_len = Math.min(f[k], right - i);
                // 从最小长度往外继续扩展
                cur_len = expand(s, i - min_len, i + min_len);
            } else {
                cur_len = expand(s, i, i);
            }
            // 记录当前i的力臂信息
            f[i] = cur_len;
            if (i + cur_len > right) {
                j = i;
                right = i + cur_len;
            }
            if (cur_len * 2 + 1 > end - start) {
                start = i - cur_len;
                end = i + cur_len;
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) != '#'){
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return (right - left - 2) / 2;
    }

    public static void main(String[] args) {
        Solution5 solution5 = new Solution5();
        System.out.println(solution5.longestPalindrome("babad"));
    }
}

